package com.umgsai.wx.backend.test;

public class LongestPalindromicSubstring1 {

    /**
     * 最长回文子串
     * https://leetcode-cn.com/problems/longest-palindromic-substring/
     *
     * @param args
     */
    public static void main(String[] args) {
//        String s = "babad";
//        String s = "cbbd";
        String s = "babad";
        String print = longestPalindrome(s);
        System.out.println(print);
    }

    public static String longestPalindrome(String s) {
        if (s == null) {
            return "";
        }
        char[] chars = s.toCharArray();
        int maxStartIndex = 0;
        int maxEndIndex = 0;

        boolean breakAll = false;
        for (int length = chars.length; length > 0; length--) {
            if (breakAll) {
                break;
            }
            for (int startIndex = 0; startIndex < chars.length; startIndex++) {
                int endIndex = startIndex + length - 1;
                if (endIndex >= chars.length) {
                    break;
                }
                if (isPalindromicSubstring(chars, startIndex, endIndex)) {
                    maxStartIndex = startIndex;
                    maxEndIndex = endIndex;
                    breakAll = true;
                    break;
                }
            }

        }
        return print(chars, maxStartIndex, maxEndIndex);
    }

    private static boolean isPalindromicSubstring(char[] chars, int startIndex, int endIndex) {
        while (startIndex <= endIndex) {
            if (chars[startIndex] != chars[endIndex]) {
                return false;
            }
            startIndex++;
            endIndex--;
        }
        return true;
    }

    private static String print(char[] chars, int startIndex, int endIndex) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = startIndex; i <= endIndex; i++) {
            stringBuilder.append(chars[i]);
        }
        return stringBuilder.toString();
    }
}
